/*!
 * # [2386.找出数组的第K大和](https://leetcode.cn/problems/find-the-k-sum-of-an-array/description/)
 *
 * @lc app=leetcode.cn id=2386 lang=rust
 *
 * ## 难度
 *
 * - Hard (42.26%)
 * - Likes:    73
 * - Dislikes: 0
 * - Total Accepted:    4.1K
 * - Total Submissions: 9.7K
 * - Testcase Example:  '[2,4,-2]\n5'
 *
 * ## 问题描述
 *
 * 给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。
 *
 * 数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）
 *
 * 返回数组的 第 k 大和 。
 *
 * 子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。
 *
 * 注意：空子序列的和视作 0 。
 *
 *
 *
 * ## 示例 1：
 *
 * - 输入：nums = [2,4,-2], k = 5
 * - 输出：2
 * - 解释：所有可能获得的子序列和列出如下，按递减顺序排列：
 *   - 6、4、4、2、2、0、0、-2
 *   - 数组的第 5 大和是 2 。
 *
 *
 * ## 示例 2：
 *
 * - 输入：nums = [1,-2,3,4,-10,12], k = 16
 * - 输出：10
 * - 解释：数组的第 16 大和是 10 。
 *
 *
 * ## 提示：
 *
 * - n == nums.length
 * - 1 <= n <= 10^5
 * - -10^9 <= nums[i] <= 10^9
 * - 1 <= k <= min(2000, 2^n)
 *
 *
 */

struct Solution;
// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 堆
    /// 1. 计算所有非负元素的和. 得到最大子序列和: sum = sum(nums[i]) (nums[i]>0);
    /// 2. 第k大子序列和为: k_max_sum = sum - k_min_abs_sum (第k-1小绝对值子序列和);
    /// 3. 为找到第k小绝对值子序列(后面的子序列都是指绝对值序列)和k_min_abs_sum, 一般需要进行如下操作:
    ///    a. 找到一种不重不漏生成所有子序列组合的方法;
    ///    b. 计算绝对值子序列的和;
    ///    c. 从小到大选择第k小的即可;
    /// 4. 上述算法存在一些问题:
    ///    a. 如何不重不漏的生成子序列?
    ///    b. 当n很大时, 生成所有子序列组合数将是O(n!)级别的, 是一个很大的消耗;
    ///       而目标只需要得到第k小的组合, 如何改进?
    ///    c. 如何快速找到第k小的子序列和?
    /// 5. 对于上述问题, 可进行如下思考:
    ///    a. 子序列有部分元素组成, 如要生成和小的和子序列, 须尽量选择绝对值小的元素组成的子序列,
    ///       为此可先将nums按绝对值从小->大排序, 从小到大依次选择;
    ///    b. 设排序后的元素分别为: n[0], n[1], n[2],.., n[i],..,
    ///       有: n[0] < n[1] < .. < n[i] < ..,
    ///       依次按 n[0], n[1], .., n[i]顺序选择元素来生成新的子序列;
    ///    c. 对于每次当前选择的元素n[i], 有两种方式来生成新的和次大的一些子序列:
    ///       - 增加n[i]到子序列中;
    ///       - 替换n[i-1];
    ///       设s: 表示选择n[i]前的子序列和, 则上述两种操作可表示为:
    ///       - s + n[i]
    ///       - s - n[i-1] + n[i]
    ///       设选择n[i]前, s为第j小的子序列和,
    ///       则, s + n[i], s-n[i-1]+n[i], 的子序列和顺序一定不大于2j
    ///    d. 为了保证能快速找到j+1小的子序列和, 可将这些新子序列和用一个最小堆min_heap缓存起来;
    ///       初始时将(s=0, i=0)入堆, s表示当前子序列和, i表示下一个要取的元素n[i]的下标;
    ///       每次进行如下操作:
    ///       a1. 弹出堆顶元素(s, i);
    ///       a2. 按照c中方式, 依次向堆中压入(s + n[i], i+1), (s-n[i-1]+n[i], i+1);
    ///       设: 第j次取出堆顶元素(s, i), 则由于每次都从堆中弹出一个元素, 而压入2个元素,
    ///       则第j次,堆中剩余的元素数为j个, 堆中已经弹出的元素为j, 而每次更新子的子序列和
    ///       不会大于第2j个最小子序列和, 因此第j+1小子序列和必定在堆中;
    ///       而由于小顶堆的性质, 此时堆顶必定为下一个最小和的子序列;
    ///    e. 由此, 循环k-1次, 从堆顶弹出的s为第k-1小子序列和;
    ///    d. 最终结果为: sum - s[k-1];
    ///    f. 题目中将堆换成大顶堆, 初始时将(sum, 0)入堆, 每次反过来计算sum-s
    /// 最小子序列生成顺序:
    /// []       [0]      [1]       [2]       [3]
    /// 00000000 00000001 00000010  00000100  00001000
    /// 								      [2,3]
    /// 								      00001100
    ///    						    [1,2]     [1,3]
    ///    						    00000110  00001010
    ///    								      [1,2,3]
    ///    								      00001110
    ///    			      [0,1]     [0,2]     [0,3]
    ///    			      00000011  00000101  00001001
    ///    			                          [0,2,3]
    ///    						  		      00001101
    ///    			                [0,1,2]   [0,1,3]
    ///    						    00000111  00001011
    ///    								      [0,1,2,3]
    ///    						              00001111
    pub fn k_sum(nums: Vec<i32>, k: i32) -> i64 {
        use std::collections::BinaryHeap;

        // 计算所有非负元素组成的最大子序列和
        let sum = nums
            .iter()
            .map(|&n| n as i64)
            .filter(|&n| n > 0)
            .sum::<i64>();

        let mut nums = nums;
        // 将nums中的所有元素按绝对值从小到大排序
        nums.sort_by(|&a, &b| a.abs().cmp(&b.abs()));

        // 设置大顶堆()
        let mut top_k_sums = BinaryHeap::<(i64, usize)>::with_capacity(k as usize);
        // 将最大序列和初始入堆
        top_k_sums.push((sum as i64, 0));
        // 依次取出1..k的大的子序列和
        for _ in 1..(k as usize) {
            // 弹出堆顶元素
            match top_k_sums.pop() {
                Some((sum, i)) => {
                    if i < nums.len() {
                        // 最小子序列和中包含nums[i]和nums[i-1]
                        top_k_sums.push(((sum - (nums[i].abs() as i64)), i + 1));
                        if i > 0 {
                            // 最小子序列和中包含nums[i], 不包含nums[i-1]
                            top_k_sums.push((
                                (sum - ((nums[i].abs() as i64) - (nums[i - 1].abs() as i64))),
                                i + 1,
                            ));
                        }
                    }
                }
                _ => {}
            }
        }

        // 前面的第k-1大序列和都弹出了
        top_k_sums.pop().unwrap().0
    }
}
// @lc code=end
